from types import List

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        cur_level = [root]
        while len(cur_level) != 0:
            tmp = []
            res_level = []
            for node in cur_level:
                res_level.append(node.val)
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            res.append(res_level)
            cur_level = tmp
        for cur in res[::2]:
            cur.reverse()
        return res
